package demo2;

import javax.swing.plaf.nimbus.AbstractRegionPainter;
import java.util.LinkedList;
import java.util.List;

public class SomeExams {

//    public ListNode head; // 表示当前链表的头节点
//
//    //创建一个链表
//    //创建链表
//    public void createList(){
//        ListNode node1 = new ListNode(12);
//        ListNode node2 = new ListNode(23);
//        ListNode node3 = new ListNode(45);
//        ListNode node4 = new ListNode(56);
//        ListNode node5 = new ListNode(76);
//
//        node1.next = node2;
//        node2.next = node3;
//        node3.next = node4;
//        node4.next = node5;
//        this.head = node1;
//    }
    //打印链表

    public void display(ListNode head) {
        ListNode cur = head;
        while (cur!=null){
            System.out.print (cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    //链表的长度
    public int size(ListNode head){
        ListNode cur = head;
        int count = 0;
        while (cur != null) {
            count ++;
            cur = cur.next;
        }
        return count;
    }

    //头插法
    public ListNode addFirst(ListNode head,int a){
        ListNode node = new ListNode(a);
        node.next = head;
        head = node;
        return head;
    }

    //反转链表
    public ListNode reverseList(ListNode head) {
        if (head==null || head.next==null){
            return head;
        }
        ListNode cur = head.next;
        head.next=null;
        while (cur!=null){
            ListNode nextCur = cur.next;
            cur.next = head;
            head = cur;
            cur = nextCur;
        }
        return head;

    }

    //找链表中间节点  -- 快慢指针
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null && fast.next!= null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;

    }


    //返回链表中倒数第k个元素   --快慢指针，快指针先走
    public ListNode FindKthToTail(ListNode head,int k) {
        ListNode cur = head;
        int count = 0;
        while (cur != null) {
            count ++;
            cur = cur.next;
        }
        if (k>0 && k<=count){
            ListNode fast = head;
            ListNode slow = head;
            for (int i=0;i<k;i++){
                fast = fast.next;
            }
            while (fast!=null){
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }
        System.out.println("FindKthToTail输入数据不合法");
        return null;
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode pA = list1;
        ListNode pB = list2;
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while (pA!=null && pB!=null){
            if (pA.val<pB.val){
                cur.next = pA;
                pA = pA.next;
                cur = cur.next;
            }else {
                cur.next = pB;
                pB = pB.next;
                cur = cur.next;
            }
        }
        if (pA == null){
            cur.next = pB;
        }else {
            cur.next = pA;
        }

        return head.next;


    }


    public ListNode partition(ListNode pHead, int x) {
       ListNode bs = null;
       ListNode be = null;
       ListNode as = null;
       ListNode ae = null;
       ListNode cur = pHead;
       while (cur!=null){
           if(cur.val<x){
               if (bs==null){
                   bs = be = cur;
               }else {
                   be.next = cur;
                   be= be.next;
               }
           }else {
               if (as==null){
                   as = ae = cur;
               }else {
                   ae.next = cur;
                   ae = ae.next;
               }
           }
           cur = cur.next;
       }
       //第一个段没有数据
       if (bs==null){
           return as;
       }
       be.next=as;
       if (ae!=null){
           ae.next=null;
       }
       return bs;



    }


    public boolean chkPalindrome(ListNode A) {
        ListNode head = A;
        ListNode fast = A;
        ListNode slow = A;
        while (fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode mid = slow;
        ListNode cur = slow.next;
        ListNode curNext = cur;
        while (cur!=null){
            curNext = cur.next;
            cur.next = mid;
            mid = cur;
            cur = curNext;
        }

        while (head != mid){
            if (head.val!= mid.val){
                return false;
            }
            if (head.next == mid){
                return true;
            }
            head = head.next;
            mid = mid.next;
        }
        return true;


    }

    //判断链表有没有环
    public boolean hasCycle(ListNode head) {
        if (head==null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;

        while (fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast==slow){
                return true;
            }
        }
        return false;

    }


    public ListNode detectCycle(ListNode head) {
        if (head==null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;

        while (fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast==slow){
                break;
            }
        }
        if (fast==null || fast.next==null){
            return null;
        }
        fast = head;
        while (fast!=slow){
            fast=fast.next;
            slow = slow.next;
        }
        return fast;




    }
}
